package com.cat.dataStructure03;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-ways-to-split-a-string/
 * @create 2025/11/10 19:45
 * @since JDK17
 */

class Solution39 {
    public int numWays(String s) {
        // 长度为n的字符串有n - 1个分割点, 可以在n - 1个分割点中任意选取两个
        char[] arr = s.toCharArray();
        List<Integer> ones = new ArrayList<>();
        int sum = 0, n = arr.length, N = (int) 1e9 + 7;
        for (int i = 0; i < n; i++) {
            if (arr[i] == '1') {
                ones.add(i);
            }
        }
        sum = ones.size();
        if (sum % 3 != 0) {
            return 0;
        }
        if (sum == 0) {
            return (int) (((long)(n - 1) * (n - 2) / 2) % N);
        }
        int idx1 = sum / 3, idx2 = sum / 3 * 2;
        int cnt1 = ones.get(idx1) - ones.get(idx1 - 1);
        int cnt2 = ones.get(idx2) - ones.get(idx2 - 1);
        return (int)(((long) cnt1 * cnt2) % N);
    }
}